//移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        //快指针找所有符合条件的数字 并把它放在慢指针处
        //如果遇到val 慢指针不动 
        int slow=0,fast=0;
        while(fast<nums.size())
        {
            if(nums[fast]!=val)
            {
                nums[slow++]=nums[fast++];
            }
            else
            {
                fast++;
            }
        }
        return slow;
    }
};
//有序数组的平方
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) 
    {
        //越小的负数平方越大 所以最后结果应该是两边大 中间小
        //同时判断首尾 平方大的往res里面插入
        int n=nums.size();
        vector<int>res(n,0);
        int l=0,r=n-1,index=n-1;
        while(l<=r && index>=0)
        {
            if(nums[l]*nums[l] < nums[r]*nums[r])
            {
                res[index--]=nums[r]*nums[r];
                r--;
            }
            else
            {
                res[index--]=nums[l]*nums[l];
                l++;
            }
        } 
        return res;
    }
};
//长度最小的子数组
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int l=0,r=0;
        int sum=0;
        int res=INT_MAX;
        for(r=0;r<nums.size();r++)
        {
            sum+=nums[r];
            while(l<=r && sum>=target)
            {
                res=min(res,r-l+1);
                sum-=nums[l++];
            }
        }
        if(res==INT_MAX) return 0;
        return res;
    }
};
//螺旋矩阵
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) 
    {
        //第一圈的起始位置 0,0  第二圈的起始位置 1,1
        //每次都填充 (当前行数-1-already)个元素 这样每次就是四圈
        //每填完一圈 already++ 
        int x,y,already=0;
        int count=1;
        int turn=n/2;
        vector<vector<int>>res(n,vector<int>(n));
        while(turn--)
        {
            int i=y;
            int j=x;
            for(i=y;i<n-already-1;i++)
            {
                res[x][i]=count++;
            }
            //此时i就是最右边那一列的列下标
            for(j=x;j<n-already-1;j++)
            {
                res[j][i]=count++;
            }
            //此时 j是最后一行的行下标 i是最后一列的列下标
            for(;i>y;i--)
            {
                res[j][i]=count++;
            }
            //此时 i是第一列的下标
            for(;j>x;j--)
            {
                res[j][i]=count++;
            }
            x++,y++,already++;
        }
        if(n%2) res[n/2][n/2]=count;
        return res;
    }
};